package com.xsherl.leetcode.solution;

import com.xsherl.leetcode.utils.PrintUtils;

import java.util.LinkedList;

public class FirstMissingPositive {

    /**
     * 对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1, N+1] 中。
     * 所以我们合理利用数组下标的功能，在当前数与数组对应的下标位置做标记，比如：nums[i] = 3, 那么我们就标记 nums[3 - 1]
     * 然后我们遍历数组，返回第一个没有标记的下标+1
     *
     * 对于标记方案有两种：
     * 1. 哈希数组：首先对负数和0进行清理，修改为N+1；
     *            然后遍历数组，修改当前数绝对值对应下标的值为负数；
     *            最后遍历数组，找出第一个值为正数的下标，返回下标+1
     *
     * 2. 置换数组：首先遍历数组，如果当前数x在[1,N]中，说明x是合法数，将x和nums[x]的值进行交换
     *             然后遍历数组，找出第一个非法值得下标，返回下标+1
     *
     *
     * 注意：时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案
     * 1 <= nums.length <= 5 * 10^5
     * -2^31 <= nums[i] <= 2^31 - 1
     */
    /**
     * 哈希数组
     */
    public int firstMissingPositive(int[] nums) {
        int len = nums.length;
        // 1. 对负数和0进行清理，修改为N+1
        for (int i = 0; i < len; ++i){
            if (nums[i] <= 0){
                nums[i] = len + 1;
            }
        }
        // 2.遍历数组，修改当前数绝对值对应下标的值为负数
        for (int i = 0; i < len; ++i){
            int index = Math.abs(nums[i]);
            if (index <= len){
                nums[index - 1] = - Math.abs(nums[index - 1]);
            }
        }
        // 3.遍历数组，找出第一个值为正数的下标，返回下标+1
        for (int i = 0; i < len; ++i){
            if (nums[i] > 0){
                return i+1;
            }
        }
        return len + 1;
    }

    /**
     * 置换数组
     */
    public int firstMissingPositive1(int[] nums) {
        int len = nums.length;
        // 1. 遍历数组，如果当前数x在[1,N]中，说明x是合法数，将x和nums[x]的值进行交换
        for (int i = 0; i < len; ++i){
            // 这里一直交换当前值，知道当前值非法或者与目标值一样时为止
            while (nums[i] > 0 && nums[i] <= len && nums[i] != nums[nums[i] - 1]){
                swap(nums, i, nums[i] - 1);
            }
        }
        PrintUtils.println(nums);
        // 2.遍历数组，找出第一个非法值得下标，返回下标+1
        for (int i = 0; i < len; ++i){
            if (nums[i] != i + 1){
                return i+1;
            }
        }
        return len + 1;
    }

    private void swap(int[] nums, int i, int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }

    public static void main(String[] args) {
        int[] nums = {3,4,-1,1};
//        int i = new FirstMissingPositive().firstMissingPositive(nums);
        int i1 = new FirstMissingPositive().firstMissingPositive1(nums);
        System.out.println(i1);
    }

}
